Search results for "Planar Graphs"

showing 2 items of 2 documents

Completely independent spanning trees in some regular graphs

2014

International audience; Let k >= 2 be an integer and T-1,..., T-k be spanning trees of a graph G. If for any pair of vertices {u, v} of V(G), the paths between u and v in every T-i, 1 <= i <= k, do not contain common edges and common vertices, except the vertices u and v, then T1,... Tk are completely independent spanning trees in G. For 2k-regular graphs which are 2k-connected, such as the Cartesian product of a complete graph of order 2k-1 and a cycle, and some Cartesian products of three cycles (for k = 3), the maximum number of completely independent spanning trees contained in these graphs is determined and it turns out that this maximum is not always k. (C) 2016 Elsevier B.V. All righ…

FOS: Computer and information sciences[ MATH ] Mathematics [math]Discrete Mathematics (cs.DM)Small Depths0102 computer and information sciences02 engineering and technology[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]01 natural sciencesCombinatoricssymbols.namesakeCompletely independent spanning treeFOS: Mathematics0202 electrical engineering electronic engineering information engineeringCartesian productDiscrete Mathematics and CombinatoricsMathematics - Combinatorics[MATH]Mathematics [math]MathematicsConstructionSpanning treeSpanning treeApplied MathematicsComplete graph020206 networking & telecommunications[ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM]Cartesian productIndependent spanning treesGraphPlanar graphPlanar Graphs010201 computation theory & mathematicssymbolsCompletely independent spanning tree.Combinatorics (math.CO)Computer Science - Discrete Mathematics
researchProduct

Decremental 2- and 3-connectivity on planar graphs

1996

We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total ofO(n logn) time under any sequence of at mostO(n) deletions. This givesO(logn) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total ofO(n log2n) time. This givesO(log2n) amortized time per deletion. The space required by all our data structures isO(n). All our time bounds improve previous bounds.

Vertex (graph theory)Discrete mathematicsDynamic data structuresAmortized analysisGeneral Computer ScienceApplied MathematicsVertex connectivityPlanar graphsData structureEdge connectivityComputer Science ApplicationsPlanar graphCombinatoricssymbols.namesakeAnalysis of algorithms Dynamic data structures Edge connectivity Planar graphs Vertex connectivitysymbolsAnalysis of algorithmsVertex connectivityDynamic data structuresAnalysis of algorithmsMathematicsAlgorithmica
researchProduct